//268. 丢失的数字
//给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

#include <stdio.h>

void FastSort(int *a,int start,int end)
{
    //终止排序
    if(start >= end)
    {
        return;
    }
    int temp = a[start];
    int left = start;
    int right = end;

    while(left < right)
    {
        while(left < right && a[right] > temp)
        {
            right--;
        }
        if(left < right)
        {
            a[left] = a[right];
            left++;
        }
        while(left < right && a[left] < temp)
        {
            left++;
        }
        if(left < right)
        {
            a[right] = a[left];
            right--;
        }
    }
    a[left] = temp;
    //递归排序
    FastSort(a,start,left-1);
    FastSort(a,right+1,end);
}

int missingNumber(int* nums, int numsSize) 
{
    int flag = 0;
    FastSort(nums,0,numsSize-1);
    int i = 0;
    for(i = 0; i < numsSize;i++)
    {
        if(nums[i] != i)
        {
            flag = 1;
            return i;
        }   
    }
    if(flag == 0)
        return i;
    return 0;
}


int main()
{
    int s[] = {0,2,4,3,5};
    printf("丢失的数是%d\n",missingNumber(s,sizeof(s)/4));
}